package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

public class No50Pow_xn_ {

    /**
     * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
     *
     * 示例 1：
     * 输入：x = 2.00000, n = 10
     * 输出：1024.00000
     * 示例 2：
     * 输入：x = 2.10000, n = 3
     * 输出：9.26100
     * 示例 3：
     * 输入：x = 2.00000, n = -2
     * 输出：0.25000
     * 解释：2-2 = 1/22 = 1/4 = 0.25
     *  
     *
     * 提示：
     * -100.0 < x < 100.0
     * -231 <= n <= 231-1
     * -104 <= xn <= 104
     */

    //参考:快速幂算法
    public double myPow(double x, int n) {
        return n<0?dg(1/x,-n):dg(x,n);
    }

    private double dg(double x,int n){

        if(n==0){
            return 1;
        }

        return dg(x*x,n/2)*((n%2==0)?1:x);
    }

    //低级版快速幂算法
    public double myPowLower(double x, int n) {

        if(n==0){
            return 1;
        }

        if(n==Integer.MIN_VALUE){
            n=Integer.MAX_VALUE;
            x=1/x;
        } else if(n<0){
            n=-n;
            x=1/x;
        }
        LowerDg(x,n);
        System.out.println(JSON.toJSONString(list));
        double sum=1;

        //如果x为负数
        for (Double d : list) {
            sum*=d;
        }

        return sum;
    }

    List<Double> list=new ArrayList<>();

    private void LowerDg(double x, int n){

        if(n==1){
            list.add(x);
            return;
        }

        int remainder=n%2;
        if(remainder!=0){
            //有余数
            list.add(x);
        }
        dg(x*x,n/2);
    }

    public static void main(String[] args) {
        No50Pow_xn_ n=new No50Pow_xn_();
        double result = n.myPow(-1.00000, -2147483648);
        System.out.println(result);
    }

}
